package top.datacluster.basic.algorithm.leetcode.stack;

import java.util.Arrays;
import java.util.Stack;

public class LeetCode496 {

    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        if (nums1.length == 0 || nums2.length == 0){
            return nums1;
        }
        Stack<NodeInde> stack = new Stack<>();
        NodeInde nodeInde = new NodeInde();
        nodeInde.data = nums2[0];
        nodeInde.index = 0;
        stack.push(nodeInde);
        int pos[] = new int[nums2.length];
        Arrays.fill(pos, -1);

        for (int i = 1; i < nums2.length; i++){
            while (!stack.isEmpty() && stack.peek().data < nums2[i]){
                nodeInde = stack.pop();
                pos[nodeInde.index] = i;
            }
            NodeInde nodeInde1 = new NodeInde();
            nodeInde1.data = nums2[i];
            nodeInde1.index = i;
            stack.push(nodeInde1);
        }
        int[] result = new int[nums1.length];
        Arrays.fill(result, -1);
        for (int i = 0; i < nums1.length; i++){
            for (int j = 0; j < nums2.length; j++){
                if (nums1[i] == nums2[j] && pos[j] != -1){
                    result[i] = nums2[pos[j]];
                    break;
                }
            }
        }
        return result;

    }

    public static void main(String[] args) {
        int[] nums1 = new int[]{137,59,92,122,52,131,79,236};
        int[] nums2 = new int[]{137,59,92,122,52,131,79,236};

        new LeetCode496().nextGreaterElement(nums1, nums2);
    }
}

class NodeInde{
    int data;
    int index;
}
